package L610;

import java.util.Arrays;

/**
 * @program: javase
 * @description: 第k大的元素
 * @author: lld
 * @create: 2021-06-10 20:06
 **/
public class Demo {
    public static void main(String[] args) {
        int[] arr={3,2,3,1,7,2,4,5,5,6};
//        int[] array = Arrays.stream(arr).distinct().toArray();
        int i = new Demo().findKthLargest(arr, 4);
//        int i = new Demo().findKthLargest(array, 4);//去重后的topK
        System.out.println(i);
        for(int j=arr.length-4;j<arr.length;j++){
            System.out.print(arr[j]+" ");
        }
    }
    public int findKthLargest(int[] nums, int k) {
//        PriorityQueue<Integer> queue=new PriorityQueue<>();
//        for(int n:nums){
//            queue.offer(n);
//            if(queue.size()>k) queue.poll();
//        }
//        return queue.peek();
        return quickSort(nums, 0, nums.length-1, nums.length-k);
    }
    public int quickSort(int[] arr,int l,int r,int index){
        int mid=partition(arr,l,r);
        if(mid==index){
            return arr[mid];
        }
        if (mid > index) {
            return quickSort(arr, l, mid - 1, index);
        } else {
            return quickSort(arr, mid + 1, r, index);
        }
    }

    public int partition(int[] arr,int left,int right){
        int p=arr[left];
        int l=left;
        while (left<right){
            while (left<right&&p<arr[right]){
                right--;
            }
            while (left<right&&p>=arr[left]){
                left++;
            }
            if(left<right){
                swap(arr, left, right);
            }
        }
        swap(arr, left, l);
        return left;
    }
    public void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}
